package com.learn.tree;

/**
 * moris遍历
 * <p>
 * 遍历的逻辑为
 * 准备两个节点，cur和mostRight
 * 1、当cur的左子树为空，cur跳到cur.right
 * 2、当cur的左子树不为空,mostRight跳到cur的左孩子的最右位置
 * a、判断MostRight.right是否为空，为空则mostRight.right = cur ,cur = cur.left
 * b.当mostRight.right不为空，且mostRight.right = cur，则mostRight.right = null,cur = cur.right
 */
public class MorisTravel {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public void moris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            //左孩子不为空
            if (mostRight != null) {
                //找左侧最右真实的右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    //找到最右孩子
                    mostRight = mostRight.right;
                }

                //如果当前最右右孩子为为空
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    mostRight.right = null;
                }

            }
            //左孩子为空，cur跳到右孩子
            cur = cur.right;
        }
    }

    /**
     * 中序遍历，当cur没有左孩子了，开始打印节点值
     *
     * @param head
     */
    public void morisIn(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            //左孩子不为空
            if (mostRight != null) {
                //找左侧最右真实的右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    //找到最右孩子
                    mostRight = mostRight.right;
                }

                //如果当前最右右孩子为为空
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }

            }
            //中序遍历，无左树打印当前值
            //左孩子为空，cur跳到右孩子
            System.out.println(cur.value);
            cur = cur.right;
        }
    }


    /**
     * 先序遍历
     *
     * @param head
     */
    public void morisPre(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            //左孩子不为空
            if (mostRight != null) {
                //找左侧最右真实的右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    //找到最右孩子
                    mostRight = mostRight.right;
                }

                //如果当前最右右孩子为为空
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    //第一次来到自己
                    System.out.println(cur.value);
                    cur = cur.left;
                    continue;
                } else {
                    //第二次到达自己
                    mostRight.right = null;
                }

            } else {
                //只能到达一次的节点
                System.out.println(cur.value);
            }
            //左孩子为空，cur跳到右孩子
            cur = cur.right;
        }
    }


    public boolean isBst(Node head) {
        if (head == null) {
            return true;
        }
        Node cur = head;
        Node mostRight = null;
        Integer pre = null;
        while (cur != null) {
            mostRight = cur.left;
            //左孩子不为空
            if (mostRight != null) {
                //找左侧最右真实的右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    //找到最右孩子
                    mostRight = mostRight.right;
                }

                //如果当前最右右孩子为为空
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }

            if (pre != null && pre >= cur.value) {
                //代表此刻cur指针需要向右子树移动，pre的当前值如果大于等于当前head头的值，则不是搜索二叉树
                return false;
            }
            pre = cur.value;
            //左孩子为空，cur跳到右孩子
            cur = cur.right;
        }
        return true;
    }
}
